package array

func lastStoneWeightII(stones []int) int {

	sum := 0
	for _, v := range stones {
		sum += v
	}
	target := sum / 2
	dp := make([]int, target+1)

	for _, w := range stones {
		for i := target; i >= w; i-- {
			if dp[i-w]+w > dp[i] {
				dp[i] = dp[i-w] + w
			}
		}
	}

	return sum - dp[target] - dp[target]

}
